use std::cmp::Ordering;
use std::mem;

/// A dynamically resizing array.
pub struct ArrayList<T> {
    data: Vec<T>,
    length: usize,
}

impl<T> ArrayList<T> {
    /// Creates a new `ArrayList` with an initial capacity.
    /// If the length is not specified, a default capacity of 16 is used.
    pub fn new(capacity: Option<usize>) -> Self {
        let initial_capacity = capacity.unwrap_or(16);
        ArrayList {
            data: Vec::with_capacity(initial_capacity),
            length: 0,
        }
    }

    /// Frees the memory used by the `ArrayList`.
    /// This is a no-op in Rust due to automatic memory management.
    pub fn free(&mut self) {
        // In Rust, dropping the `ArrayList` will automatically free resources.
        self.data.clear();
        self.length = 0;
    }

    /// Inserts an element at the specified index.
    /// Returns `true` if the insertion was successful, otherwise `false`.
    pub fn insert(&mut self, index: usize, value: T) -> bool {
        if index > self.length {
            return false;
        }

        // Ensure there is enough capacity.
        if self.length == self.data.capacity() {
            self.enlarge();
        }

        // Move elements to the right to make space for the new element.
        self.data.insert(index, value);
        self.length += 1;
        true
    }

    /// Appends an element to the end of the list.
    pub fn append(&mut self, value: T) -> bool {
        self.insert(self.length, value)
    }

    /// Prepends an element to the beginning of the list.
    pub fn prepend(&mut self, value: T) -> bool {
        self.insert(0, value)
    }

    /// Removes a range of elements from the list.
    pub fn remove_range(&mut self, index: usize, length: usize) {
        if index >= self.length || index + length > self.length {
            return;
        }

        self.data.drain(index..index + length);
        self.length -= length;
    }

    /// Removes a single element at the specified index.
    pub fn remove(&mut self, index: usize) {
        self.remove_range(index, 1);
    }

    /// Finds the index of the first element that matches the given value.
    /// Returns `Some(index)` if found, otherwise `None`.
    pub fn index_of<F>(&self, callback: F, value: &T) -> Option<usize>
    where
        F: Fn(&T, &T) -> bool,
    {
        self.data.iter().position(|x| callback(x, value))
    }

    /// Clears the list, removing all elements.
    pub fn clear(&mut self) {
        self.data.clear();
        self.length = 0;
    }

    /// Sorts the list using the provided comparison function.
    pub fn sort<F>(&mut self, compare_func: F)
    where
        F: Fn(&T, &T) -> Ordering,
    {
        self.data[..self.length].sort_by(compare_func);
    }

    /// Enlarges the capacity of the list by doubling its current capacity.
    fn enlarge(&mut self) {
        let new_capacity = self.data.capacity().checked_mul(2).unwrap_or(usize::MAX);
        self.data.reserve(new_capacity - self.data.capacity());
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_new_arraylist() {
        let list: ArrayList<i32> = ArrayList::new(Some(10));
        assert_eq!(list.data.capacity(), 10);
        assert_eq!(list.length, 0);
    }

    #[test]
    fn test_insert_and_append() {
        let mut list = ArrayList::new(None);
        assert!(list.append(1));
        assert!(list.insert(0, 2));
        assert_eq!(list.length, 2);
        assert_eq!(list.data[0], 2);
        assert_eq!(list.data[1], 1);
    }

    #[test]
    fn test_remove() {
        let mut list = ArrayList::new(None);
        list.append(1);
        list.append(2);
        list.append(3);
        list.remove(1);
        assert_eq!(list.length, 2);
        assert_eq!(list.data[0], 1);
        assert_eq!(list.data[1], 3);
    }

    #[test]
    fn test_index_of() {
        let mut list = ArrayList::new(None);
        list.append(1);
        list.append(2);
        list.append(3);
        let index = list.index_of(|a, b| a == b, &2);
        assert_eq!(index, Some(1));
    }

    #[test]
    fn test_sort() {
        let mut list = ArrayList::new(None);
        list.append(3);
        list.append(1);
        list.append(2);
        list.sort(|a, b| a.cmp(b));
        assert_eq!(list.data, vec![1, 2, 3]);
    }
}
